package com.dy.数组.高级.滑动窗口最大值;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;

/*
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。

返回滑动窗口最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
注意：

你可以假设 k 总是有效的，1 ≤ k ≤ 输入数组的大小，且输入数组不为空。

进阶：

你能在线性时间复杂度内解决此题吗？
 */
public class Solution {
    //构建最大堆，每次进来一个，就删除前面一个
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) return nums;
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        //输入前k个
        for (int i = 0; i < k; i++) {
            pq.add(nums[i]);
        }
        int[] res = new int[nums.length - k + 1];
        res[0] = pq.peek();
        //i是结果的指针，j是nums的指针
        /*
        0 1 2 3 4    k=3
        当j=4时,
         */
        for (int i = 1, j = k; j < nums.length; i++, j++) {
            pq.remove(nums[j - k]);
            pq.add(nums[j]);
            res[i] = pq.peek();
        }
        return res;
    }
    //双向队列

    /**
     * 在队列中维持一个k长度窗口内的递减元素下标，为什么呢？因为当元素递增时，前面的元素就不需要了，因为最大值肯定不会是它们了。
     * <p>
     * 顺序扫描每一个元素，当队头的元素超出窗口视野的时候，将对头元素出队；然后检查队尾，如果队尾元素小于或等于当前元素，
     * 则队尾元素出队，重复检查队尾直至队列为空或者队尾元素大于当前元素。然后当前元素入队。
     * ---------------------
     */
    public int[] maxSlidingWindow2(int[] nums, int k) {
        if (nums.length == 0) return nums;
        LinkedList<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            // 每当新数进来时，如果发现队列头部的数的下标，是窗口最左边数的下标，则扔掉
            if (!deque.isEmpty() && deque.peekFirst() == i - k) deque.pollFirst();
            // 把队列尾部所有比新数小的都扔掉，保证队列是降序的
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast();
            // 加入新数
            deque.addLast(i);
            // 队列头部就是该窗口内第一大的
            if (i + 1 >= k) res[i - k + 1] = nums[deque.peek()];
        }
        return res;

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] r = {1, 3, -1, -3, 5, 3, 6, 7};
        solution.maxSlidingWindow2(r, 3);
    }
}
